Real or Natural numbers interpretations and their effect on complexity
Identifieur interne : 000686 ( Main/Exploration ); précédent : 000685; suivant : 000687Real or Natural numbers interpretations and their effect on complexity
Auteurs : Guillaume Bonfante [France] ; Florian Deloup [France] ; Antoine Henrot [France]Source :
- Theoretical Computer Science [ 0304-3975 ] ; 2015.
English descriptors
Abstract
Interpretation methods have been introduced in the 70’s byLankford in rewriting theory to prove termination. Actually, as shown byBonfante et al., they provide some good tools to prove the complexity ofprograms. However, such an analysis depends deeply on the archimedeanproperty of natural numbers. This is in contradiction with the fact thatfinding an interpretation can be solved by Tarski’s decision procedure(as described by Dershowitz), and consequently interpretations areusually chosen over the reals rather than over the integers. Doing so,one cannot use anymore the (good) properties of the natural(welordering of N used to bound the complexity of programs. We provethat one may benefit from the best of both worlds: the complexityanalysis still holds even with real numbers. The reason lies in a deepalgebraic property of polynomials over the reals. We illustrate this bytwo characterizations, one of polynomial time and one of polynomial space.
Url:
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 003F65
- to stream Hal, to step Curation: 003F65
- to stream Hal, to step Checkpoint: 000674
- to stream Main, to step Merge: 000782
- to stream Main, to step Curation: 000686
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Real or Natural numbers interpretations and their effect on complexity</title><author><name sortKey="Bonfante, Guillaume" sort="Bonfante, Guillaume" uniqKey="Bonfante G" first="Guillaume" last="Bonfante">Guillaume Bonfante</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-29797" status="VALID"><idno type="RNSR">200918992J</idno><orgName>Theoretical adverse computations, and safety</orgName><orgName type="acronym">CARTE</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/carte</ref></desc><listRelation><relation active="#struct-129671" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-423084" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno><orgName>INRIA Nancy - Grand Est</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/nancy</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-423084" type="direct"><org type="department" xml:id="struct-423084" status="VALID"><orgName>Department of Formal Methods </orgName><orgName type="acronym">LORIA - FM</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/formal-methods</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><settlement type="city">Metz</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Deloup, Florian" sort="Deloup, Florian" uniqKey="Deloup F" first="Florian" last="Deloup">Florian Deloup</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-1954" status="VALID"><orgName>Institut de Mathématiques de Toulouse UMR5219</orgName><orgName type="acronym">IMT</orgName><desc><address><addrLine>UPS IMT, F-31062 Toulouse Cedex 9, France INSA, F-31077 Toulouse, France UT1, F-31042 Toulouse, France UT2, F-31058 Toulouse, France</addrLine><country key="FR"></country></address><ref type="url">https://www.math.univ-toulouse.fr/</ref></desc><listRelation><relation active="#struct-81148" type="direct"></relation><relation active="#struct-116256" type="direct"></relation><relation active="#struct-217752" type="direct"></relation><relation active="#struct-301089" type="direct"></relation><relation active="#struct-413500" type="direct"></relation><relation active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-81148" type="direct"><org type="institution" xml:id="struct-81148" status="VALID"><orgName>Université Toulouse 1 Capitole</orgName><orgName type="acronym">UT1</orgName><desc><address><addrLine>2 rue du Doyen-Gabriel-Marty - 31042 Toulouse Cedex 9 </addrLine><country key="FR"></country></address><ref type="url">http://www.ut-capitole.fr/</ref></desc></org></tutelle><tutelle active="#struct-116256" type="direct"><org type="institution" xml:id="struct-116256" status="VALID"><idno type="IdRef">026403994</idno><orgName>Université Toulouse 2</orgName><orgName type="acronym">UT2</orgName><date type="start">1971-01-01</date><desc><address><addrLine>5 allées Antonio Machado - 31058 Toulouse Cedex 9 </addrLine><country key="FR"></country></address><ref type="url">http://www.univ-tlse2.fr</ref></desc></org></tutelle><tutelle active="#struct-217752" type="direct"><org type="institution" xml:id="struct-217752" status="VALID"><orgName>Université Paul Sabatier - Toulouse 3</orgName><orgName type="acronym">UPS</orgName><desc><address><addrLine>118 route de Narbonne - 31062 Toulouse</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-tlse3.fr/</ref></desc></org></tutelle><tutelle active="#struct-301089" type="direct"><org type="institution" xml:id="struct-301089" status="VALID"><orgName>PRES Université de Toulouse</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-413500" type="direct"><org type="institution" xml:id="struct-413500" status="INCOMING"><orgName>Institut National des Sciences Appliquées de Toulouse</orgName><orgName type="acronym">INSA de Toulouse</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country></affiliation></author><author><name sortKey="Henrot, Antoine" sort="Henrot, Antoine" uniqKey="Henrot A" first="Antoine" last="Henrot">Antoine Henrot</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-388636" status="VALID"><orgName>Equations aux dérivées partielles</orgName><orgName type="acronym">EDP</orgName><desc><address><country key="FR"></country></address><ref type="url">http://iecl.univ-lorraine.fr/equipesIECL_edp.html</ref></desc><listRelation><relation active="#struct-211251" type="direct"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7502" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-211251" type="direct"><org type="laboratory" xml:id="struct-211251" status="VALID"><idno type="IdRef">180064606</idno><idno type="RNSR">199712570F</idno><idno type="IdUnivLorraine">[UL]RSB--</idno><orgName>Institut Élie Cartan de Lorraine</orgName><orgName type="acronym">IECL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Université de Lorraine, Boulevard des Aiguillettes BP 70239 54506 Vandoeuvre-les-Nancy CedexIle du Saulcy - 57 045 Metz Cedex 01</addrLine><country key="FR"></country></address><ref type="url">http://iecl.univ-lorraine.fr/</ref></desc><listRelation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7502" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7502" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><settlement type="city">Metz</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université de Lorraine</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:hal-01093579</idno><idno type="halId">hal-01093579</idno><idno type="halUri">https://hal.archives-ouvertes.fr/hal-01093579</idno><idno type="url">https://hal.archives-ouvertes.fr/hal-01093579</idno><date when="2015">2015</date><idno type="wicri:Area/Hal/Corpus">003F65</idno><idno type="wicri:Area/Hal/Curation">003F65</idno><idno type="wicri:Area/Hal/Checkpoint">000674</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000674</idno><idno type="wicri:doubleKey">0304-3975:2015:Bonfante G:real:or:natural</idno><idno type="wicri:Area/Main/Merge">000782</idno><idno type="wicri:Area/Main/Curation">000686</idno><idno type="wicri:Area/Main/Exploration">000686</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Real or Natural numbers interpretations and their effect on complexity</title><author><name sortKey="Bonfante, Guillaume" sort="Bonfante, Guillaume" uniqKey="Bonfante G" first="Guillaume" last="Bonfante">Guillaume Bonfante</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-29797" status="VALID"><idno type="RNSR">200918992J</idno><orgName>Theoretical adverse computations, and safety</orgName><orgName type="acronym">CARTE</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/carte</ref></desc><listRelation><relation active="#struct-129671" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-423084" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno><orgName>INRIA Nancy - Grand Est</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/nancy</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-423084" type="direct"><org type="department" xml:id="struct-423084" status="VALID"><orgName>Department of Formal Methods </orgName><orgName type="acronym">LORIA - FM</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/formal-methods</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><settlement type="city">Metz</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Deloup, Florian" sort="Deloup, Florian" uniqKey="Deloup F" first="Florian" last="Deloup">Florian Deloup</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-1954" status="VALID"><orgName>Institut de Mathématiques de Toulouse UMR5219</orgName><orgName type="acronym">IMT</orgName><desc><address><addrLine>UPS IMT, F-31062 Toulouse Cedex 9, France INSA, F-31077 Toulouse, France UT1, F-31042 Toulouse, France UT2, F-31058 Toulouse, France</addrLine><country key="FR"></country></address><ref type="url">https://www.math.univ-toulouse.fr/</ref></desc><listRelation><relation active="#struct-81148" type="direct"></relation><relation active="#struct-116256" type="direct"></relation><relation active="#struct-217752" type="direct"></relation><relation active="#struct-301089" type="direct"></relation><relation active="#struct-413500" type="direct"></relation><relation active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-81148" type="direct"><org type="institution" xml:id="struct-81148" status="VALID"><orgName>Université Toulouse 1 Capitole</orgName><orgName type="acronym">UT1</orgName><desc><address><addrLine>2 rue du Doyen-Gabriel-Marty - 31042 Toulouse Cedex 9 </addrLine><country key="FR"></country></address><ref type="url">http://www.ut-capitole.fr/</ref></desc></org></tutelle><tutelle active="#struct-116256" type="direct"><org type="institution" xml:id="struct-116256" status="VALID"><idno type="IdRef">026403994</idno><orgName>Université Toulouse 2</orgName><orgName type="acronym">UT2</orgName><date type="start">1971-01-01</date><desc><address><addrLine>5 allées Antonio Machado - 31058 Toulouse Cedex 9 </addrLine><country key="FR"></country></address><ref type="url">http://www.univ-tlse2.fr</ref></desc></org></tutelle><tutelle active="#struct-217752" type="direct"><org type="institution" xml:id="struct-217752" status="VALID"><orgName>Université Paul Sabatier - Toulouse 3</orgName><orgName type="acronym">UPS</orgName><desc><address><addrLine>118 route de Narbonne - 31062 Toulouse</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-tlse3.fr/</ref></desc></org></tutelle><tutelle active="#struct-301089" type="direct"><org type="institution" xml:id="struct-301089" status="VALID"><orgName>PRES Université de Toulouse</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-413500" type="direct"><org type="institution" xml:id="struct-413500" status="INCOMING"><orgName>Institut National des Sciences Appliquées de Toulouse</orgName><orgName type="acronym">INSA de Toulouse</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country></affiliation></author><author><name sortKey="Henrot, Antoine" sort="Henrot, Antoine" uniqKey="Henrot A" first="Antoine" last="Henrot">Antoine Henrot</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-388636" status="VALID"><orgName>Equations aux dérivées partielles</orgName><orgName type="acronym">EDP</orgName><desc><address><country key="FR"></country></address><ref type="url">http://iecl.univ-lorraine.fr/equipesIECL_edp.html</ref></desc><listRelation><relation active="#struct-211251" type="direct"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7502" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-211251" type="direct"><org type="laboratory" xml:id="struct-211251" status="VALID"><idno type="IdRef">180064606</idno><idno type="RNSR">199712570F</idno><idno type="IdUnivLorraine">[UL]RSB--</idno><orgName>Institut Élie Cartan de Lorraine</orgName><orgName type="acronym">IECL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Université de Lorraine, Boulevard des Aiguillettes BP 70239 54506 Vandoeuvre-les-Nancy CedexIle du Saulcy - 57 045 Metz Cedex 01</addrLine><country key="FR"></country></address><ref type="url">http://iecl.univ-lorraine.fr/</ref></desc><listRelation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7502" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7502" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><settlement type="city">Metz</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université de Lorraine</orgName></affiliation></author></analytic><series><title level="j">Theoretical Computer Science</title><idno type="ISSN">0304-3975</idno><imprint><date type="datePub">2015</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>Algebraic Geometry</term><term>Complexity Theory</term><term>Interpretation</term><term>Polynomial Time</term><term>rewriting</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Interpretation methods have been introduced in the 70’s byLankford in rewriting theory to prove termination. Actually, as shown byBonfante et al., they provide some good tools to prove the complexity ofprograms. However, such an analysis depends deeply on the archimedeanproperty of natural numbers. This is in contradiction with the fact thatfinding an interpretation can be solved by Tarski’s decision procedure(as described by Dershowitz), and consequently interpretations areusually chosen over the reals rather than over the integers. Doing so,one cannot use anymore the (good) properties of the natural(welordering of N used to bound the complexity of programs. We provethat one may benefit from the best of both worlds: the complexityanalysis still holds even with real numbers. The reason lies in a deepalgebraic property of polynomials over the reals. We illustrate this bytwo characterizations, one of polynomial time and one of polynomial space.</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Grand Est</li><li>Lorraine (région)</li></region><settlement><li>Metz</li><li>Nancy</li></settlement><orgName><li>Université de Lorraine</li></orgName></list><tree><country name="France"><region name="Grand Est"><name sortKey="Bonfante, Guillaume" sort="Bonfante, Guillaume" uniqKey="Bonfante G" first="Guillaume" last="Bonfante">Guillaume Bonfante</name></region><name sortKey="Deloup, Florian" sort="Deloup, Florian" uniqKey="Deloup F" first="Florian" last="Deloup">Florian Deloup</name><name sortKey="Henrot, Antoine" sort="Henrot, Antoine" uniqKey="Henrot A" first="Antoine" last="Henrot">Antoine Henrot</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000686 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000686 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= Hal:hal-01093579
|texte= Real or Natural numbers interpretations and their effect on complexity
}}
| This area was generated with Dilib version V0.6.33. |  |